package 算法;

import java.util.*;

public class 排序和搜索 {
    /**
     * 颜色分类
     * 给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
     *
     * 必须在不使用库的sort函数的情况下解决这个问题。
     *
     *
     * 示例 1：
     *
     * 输入：nums = [2,0,2,1,1,0]
     * 输出：[0,0,1,1,2,2]
     * 示例 2：
     *
     * 输入：nums = [2,0,1]
     * 输出：[0,1,2]
     *
     * 提示：
     *
     * n == nums.length
     * 1 <= n <= 300
     * nums[i] 为 0、1 或 2
     *
     * 进阶：
     *
     * 你可以不使用代码库中的排序函数来解决这道题吗？
     * 你能想出一个仅使用常数空间的一趟扫描算法吗？
     *
     * @param nums
     */
    //三指针
    public void sortColors(int[] nums) {
        //0的右边界
        int left = 0;
        //2的左边界
        int right = nums.length - 1;
        //指向当前数字
        int index = 0;
        while (index <= right) {
            if (nums[index] == 0) {
                //如果是0，就往前面移
                swap(nums, left++, index++);
            } else if (nums[index] == 1) {
                index++;
            } else if (nums[index] == 2) {
                //如果是2就往后面移
                swap(nums, right--, index);
            }
        }
    }

    //交换数组中的两个数字
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /**
     * 前k个高频元素
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     *
     * 示例 1:
     *
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 示例 2:
     *
     * 输入: nums = [1], k = 1
     * 输出: [1]
     *
     * 提示：
     *
     * 1 <= nums.length <= 105
     * k 的取值范围是 [1, 数组中不相同的元素的个数]
     * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
     *
     * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {

        //先统计每个数字出现的次数
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1); //getOrDefault：获取当前索引值，如果该值不存在则返回默认值
        }

        //最大堆
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((a, b)->b[1]-a[1]);
        for(int key:map.keySet()){
            priorityQueue.add(new int[]{key,map.get(key)});
        }

        //取堆中最大的k个元素
        int res[]=new int[k];
        for(int i=0;i<k;i++){
            res[i]=priorityQueue.poll()[0]; //获取key
        }
        return res;
    }

    /**
     * 数组中的第k个最大元素
     *
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 示例 1:
     *
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 示例2:
     *
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     *
     * 提示：
     *
     * 1 <= k <= nums.length <= 104
     * -104<= nums[i] <= 104
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        // 1、先排序，后取值
        // Arrays.sort(nums);
        // return nums[nums.length-k];
        //
        //2、最小堆
        // PriorityQueue<Integer> queue = new PriorityQueue<>();//默认最小堆
        // for (int val : nums) {
        //     queue.add(val);//加入堆中
        //     //如果堆中元素大于k，则把堆顶元素给移除
        //     if (queue.size() > k)
        //         queue.poll();
        // }
        // return queue.peek();//返回堆顶元素
        //
        //3、最大堆
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->b-a);
        for(int num:nums){
            priorityQueue.add(num);
        }
        for(int i=0;i<k-1;i++){
            priorityQueue.poll();
        }
        return priorityQueue.poll();
    }

    /**
     * 寻找峰值
     * 峰值元素是指其值严格大于左右相邻值的元素。
     *
     * 给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     *
     * 你可以假设nums[-1] = nums[n] = -∞ 。
     *
     * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,3,1]
     * 输出：2
     * 解释：3 是峰值元素，你的函数应该返回其索引 2。
     * 示例2：
     *
     * 输入：nums = [1,2,1,3,5,6,4]
     * 输出：1 或 5
     * 解释：你的函数可以返回索引 1，其峰值元素为 2；
     *     或者返回索引 5， 其峰值元素为 6。
     *
     * 提示：
     *
     * 1 <= nums.length <= 1000
     * -231 <= nums[i] <= 231 - 1
     * 对于所有有效的 i 都有 nums[i] != nums[i + 1]
     *
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        // 1、找出开始下降的点
        // int index=0;
        // while(index<nums.length-1&&nums[index]<nums[index+1]){
        //     index++;
        // }
        // return index;

        //2、直接遍历比较
        for (int i = 0; i < nums.length; i++) {
            if(i - 1 >=0 && nums[i - 1] > nums[i])
                continue;
            if(i + 1 < nums.length && nums[i + 1] > nums[i])
                continue;
            return i;
        }
        return -1;

    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     *
     * 如果数组中不存在目标值 target，返回[-1, -1]。
     *
     * 你必须设计并实现时间复杂度为O(log n)的算法解决此问题。
     *
     *
     * 示例 1：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例2：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     *
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     *
     * 提示：
     *
     * 0 <= nums.length <= 105
     * -109<= nums[i]<= 109
     * nums是一个非递减数组
     * -109<= target<= 109
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int length=nums.length;
        int p=0;
        int q=length-1;
        while(p<=q){
            while(p<=q&&nums[p]!=target){
                ++p;//++p,减少内存空间的使用，提高效率
            }
            while(p<=q&&nums[q]!=target){
                --q;
            }
            if(p<=q){//防止出现当目标值在数组中不存在时，p>q情况
                return new int[]{p,q};
            }
        }
        return new int[]{-1,-1};
    }

    /**
     * 合并区间
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     *
     *
     * 示例 1：
     *
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     * 示例2：
     *
     * 输入：intervals = [[1,4],[4,5]]
     * 输出：[[1,5]]
     * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
     *
     * 提示：
     *
     * 1 <= intervals.length <= 104
     * intervals[i].length == 2
     * 0 <= starti <= endi <= 104
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0){
            return intervals;
        }
        //按照二维数组的第一个数组大小排列
        Arrays.sort(intervals, Comparator.comparingInt(o->o[0]));//以子数组第一个数进行排序
        //创建一个arraylist用来接收结果，因为结果的个数不确定
        List<int[]> list=new ArrayList<>();
        int[] temp=intervals[0];
        for(int i=0;i<intervals.length;i++){
            //判断第一个数组第二个数是否大一第二个数组的第一个数
            if(temp[1]>=intervals[i][0]){//两数组有交集
                temp[1]=Math.max(temp[1],intervals[i][1]);
            }else{
                list.add(temp);//两数组无交集
                temp=intervals[i];
            }
        }
        list.add(temp);//上述循环没有走else，意味着两数组有交集
        return list.toArray(new int[list.size()][2]);
    }

    /**
     * 搜索旋转排序数组
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     *
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     *
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     *
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     *
     *
     * 示例 1：
     *
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     * 示例2：
     *
     * 输入：nums = [4,5,6,7,0,1,2], target = 3
     * 输出：-1
     * 示例 3：
     *
     * 输入：nums = [1], target = 0
     * 输出：-1
     *
     * 提示：
     *
     * 1 <= nums.length <= 5000
     * -104 <= nums[i] <= 104
     * nums 中的每个值都 独一无二
     * 题目数据保证 nums 在预先未知的某个下标上进行了旋转
     * -104 <= target <= 104
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int res=-1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                res=i;
                break;
            }
        }
        return res;
    }

    /**
     * 搜索二维矩阵 II
     * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     *
     * 每行的元素从左到右升序排列。
     * 每列的元素从上到下升序排列。
     *  
     *
     * 示例 1：
     *
     *
     * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
     * 输出：true
     * 示例 2：
     *
     *
     * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
     * 输出：false
     *  
     *
     * 提示：
     *
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= n, m <= 300
     * -109 <= matrix[i][j] <= 109
     * 每行的所有元素从左到右升序排列
     * 每列的所有元素从上到下升序排列
     * -109 <= target <= 109
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int p=0;
        int q=matrix[0].length-1;//依据题意，q为某行中最后一个数，即该行最大值
        while(p<matrix.length&&q>=0){
            if(matrix[p][q]>target){//此处matrix[p][q]表示该行最大的数
                q--;//该行最大数大于target，往前移
            }else if(matrix[p][q]<target){
                p++;//该行最大数小于target，往下移
            }else{
                return true;
            }
        }
        return false;
    }

}
